“Binary like Yin & Yang”

The Divide and Conquer Paradigm

The main idea of Divide and Conquer is that we can tackle a big problem by solving smaller sub-problems and then merging this solutions together to get an answer. The genius part about all of this is that if we can find sub-problems that are similar to the original problem, then we can also use divide and conquer to solve the smaller problems.

There are usually three steps in divide and conquer:

Today we will learn about one of the most popular Divide and Conquer algorithms: Binary Search.

Motivation

Let’s say that you need to find the position of a value in an array. How would you do it?

The most intuitive way of approaching this problem is to go through all elements in an array and check if it is the one you are looking for.

#include <bits/stdc++.h>

using namespace std;

int main () {
  int num = 10;
  int x=20;
  int arr[]={2,4,6,7,8,10,20,4034,4535,5635435,577436536};

  for (int i = 0; i < 10; i++) {
    if (arr[i] == x) {
      cout << i+1 << endl;
      break;
    }
  }

  if (i==10) {
    cout<<x<<" is not in the array"<<endl;
  }
    
  return (0);
}

It is very simple to see that this approach has a complexity of \(O(n)\). In general, this complexity is pretty good, however looking for a specific element in an array is a basic operation that usually needs to be done more than once. What happens if we do this linear search thousands of times? How many times can we do it without exceeding the time limit? Is there a better way?

Binary Search

There is a better way and it’s called Binary Search. This is one of the most basic and powerful concepts, as it can be used in thousands of algorithms to boost up the performance significantly. Most importantly, as we will see, its uses go beyond searching for an element in an array. The only condition that needs to hold for binary search to work is that the array (or our search domain) must be sorted.

First Approach

#include <bits/stdc++.h>

using namespace std;

int binary_search(int *arr, int size, int x){
  int left = 0;
  right = size - 1;

  while (left <= right) {
    int med = left + (right-left) / 2;

    if (arr[med] == x) {
      return med;
    }
    else if (arr[med] > x) {
      right = med - 1;
    }
    else {
      left = med+1;
    }
  }

  return -1;
}

Now, what happen if there exists many equal values in the array. What position does the binary method return?

  int arr[] = {2,4,6,7,8,10,10,10,20,4034,4535,5635435,577436536};

In this cases we need more information in order to determine what value we must return. Even though in many problems it doesn’t matter which we pick, in many others it will. For that cases, we are going to work with lower and upper bound.

Lower Bound

The lower bound is the first element that does not compare less than the value we are looking for. In simpler words, is the first occurrence of the search value. The following is a possible implementation of lower bound, however, std::lower_bound can simplify things for us.

#include <bits/stdc++.h>

using namespace std;,

int binary_search(int *arr, int size, int x) {
  int left = 0;
  int right = size - 1;

  int pos = -1;
  while (left < right) {
    int med = left + (right - left) / 2;
    if (arr[med] == x) {
      pos = med;
    }
    if (arr[med] >= x) {
      right = med;
    }
    else {
      left = med + 1;
    }
  }

  return pos;
}

Upper Bound

This is the last element that compares less than or equal to our value. Similarly, it can be found using the following algorithm:

#include <bits/stdc++.h>

using namespace std;

int binary_search(int *arr, int size, int x){
  int left = 0;
  int right = size - 1;

  int pos = -1;
  while (left < right) {
    int med = left + (right - left + 1) / 2;
    if (arr[med] == x) {
      pos = med;
    }
    if (arr[med] >= x) {
      right = med - 1;
    }
    else {
      left = med;
    }
  }

  return pos;
}
Away form Arrays

As it was mentioned before, binary search is not only useful for finding values in an array, but it also has other uses. In this section we will explore some of these.

Solving an Equation

Let’s say we want to solve the equation: \(f(x) = ax^3 + bx^2 + cx + d = e\), where \(a, b, c, d, e > 0\). The answer must be right to 4 decimal places. How can we do this efficiently?

We can use binary search to solve this in \(O(logn)\) time. The key idea is to realize that \(f\) is a increasing function, and therefore \(x_a \leq x_b \rightarrow f(x_a) \leq f(x_b)\). Therefore we can run a binary search in \(x\) in order to find the answer. However our binary search will be slightly different, as now we don’t need to find a precise answer, but one with a precision of 4 decimal places. This means that we want to find an x such that \(|e - f(x)| > 0.0001\).

Searching for the Answer

Let’s consider the following problem: https://onlinejudge.org/external/120/12032.pdf

The key thing is to realize that if we can reach the top with some an initial strength \(k_0\), then any initial strength \(k, k > k_0\) can also reach the top. Therefore we can use binary search to look for the minimum value of \(k\) that reaches the top from 1 to \(r + 1\). As we can determine for a given \(k\) if it is possible to reach the top, then this solution would have a complexity of \(O(nlog(r + 1))\).